【题解】 [APIO2010]特别行动队斜率优化DP luoguP3628

依旧是斜率优化的套路。

设 $f_i$ 表示前 $i$ 个士兵的最大贡献，转移显然是枚举一个 $j$ ，将 $j+1$ 到 $i$ 这些士兵组成特别行动队算贡献：

$f_i=\max\{f_j+a(s_i-s_j)^2+b(s_i-s_j)+c\}$

其中 $s_i$ 为战斗力的前缀和。这个方程是 $O(n^2)$ 的，需要优化。发现这个转移式貌似不满足单调队列优化的条件，于是将中间的式子拆开看看可不可以斜率优化。

$f_i=\max\{f_j+a(s_i^2+s_j^2-2s_is_j)+b\cdot s_i-b\cdot s_j+c\}\\f_i=\max\{f_j+a\cdot s_i^2+a\cdot s_j^2-2a\cdot s_is_j)+b\cdot s_i-b\cdot s_j+c\}\\f_i=f_j+a\cdot s_i^2+a\cdot s_j^2-2a\cdot s_is_j+b\cdot s_i-b\cdot s_j+c\\f_j+a\cdot s_i^2+a\cdot s_j^2+b\cdot s_i-b\cdot s_j+c=2a\cdot s_i\cdot s_j +f_i$

诶，是 $y=kx+b$ 的形式，而且满足斜率优化的条件诶。继续将 $x,y$ 找出来放到坐标系上( $x=s_j$ , $y=f_j+a\cdot s_j^2-b\cdot s_j$ ) 。

因为是 $\max$ ，所以用单调队列维护一下上凸壳然后转移即可，复杂度 $O(n)$ 。

Code:

#include <cstdio>
#include <iostream>
#define S(x) ((x)*(x))
using namespace std;

const int N=1e6+2;
int n,a,b,c,head,tail;
long long s[N],f[N],q[N];

template <typename _Tp> inline void IN(_Tp&x) {
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch)) if(ch=='-') flag=1;
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    if(flag) x=-x;
}

double X(int i) {return s[i];}
double Y(int i) {return f[i]+1ll*S(s[i])*a-1ll*s[i]*b;}
double slope(int i,int j) {return (Y(j)-Y(i))/(X(j)-X(i));}
inline void calc(int i,int j) {
    f[i]=f[j]+1ll*S(s[i]-s[j])*a+1ll*(s[i]-s[j])*b+c;
}

int main() {
    IN(n),IN(a),IN(b),IN(c);
    for(int i=1;i<=n;++i) IN(s[i]),s[i]+=s[i-1];
    for(int i=1;i<=n;++i) {
        while(head<tail&&slope(q[head],q[head+1])>2*a*s[i]) ++head;
        calc(i,q[head]);
        while(head<tail&&slope(q[tail],i)>slope(q[tail],q[tail-1])) --tail;
        q[++tail]=i;
    }
    printf("%lld\n",f[n]);
    return 0;
}

本文标题:【题解】 [APIO2010]特别行动队斜率优化DP luoguP3628

文章作者:Qiuly

发布时间:2019年04月24日 - 00:00

最后更新:2019年04月28日 - 13:52

原始链接:http://qiulyblog.github.io/2019/04/24/[题解]luoguP3628/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际转载请保留原文链接及作者。